public class LeetCode724 {
    public static void main(String[] args) {

        System.out.println(pivotIndex1(new int[]{1, 7, 3, 6, 5, 6}));
        System.out.println(pivotIndex1(new int[]{1, 2, 3}));
        System.out.println(pivotIndex1(new int[]{2, 1, -1}));
        System.out.println(pivotIndex1(new int[]{-1,-1,-1,-1,-1,0}));
    }

    /**
     * 只能用于全部是正数的情况
     * @param nums
     * @return
     */
    public static int pivotIndex(int[] nums) {
        int left = 0;

        int size = nums.length;
        int right = size - 1;

        int leftSum = 0;
        int rightSum = nums[right];
        while (left < right - 1 ){
            if(leftSum > rightSum){
                rightSum += nums[--right];
                System.out.println("1 left:" + left + "  right:" + right + " leftsum:" + leftSum + "  rightsum:" + rightSum);
                continue;
            }

            if(leftSum < rightSum){
                leftSum += nums[left++];
                System.out.println("2 left:" + left + "  right:" + right + " leftsum:" + leftSum + "  rightsum:" + rightSum);
                continue;
            }

            if(leftSum == rightSum && left < right - 1){
                rightSum += nums[--right];
                System.out.println("3 left:" + left + "  right:" + right + " leftsum:" + leftSum + "  rightsum:" + rightSum);
            }else{
                return -1;
            }
        }

        if(leftSum == rightSum){
            return right - 1;
        }

        return -1;
    }

    public static int pivotIndex1(int[] nums) {
        int size = nums.length;

        int[] preSum = new int[size + 1];
        preSum[0] = 0;

        for (int i = 1; i <= size; i++){
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }

        for (int pre : preSum){
            System.out.print(pre + " ");
        }
        System.out.println();

        for (int k = 0; k < size; k++){
            if(preSum[k] == (preSum[size] - preSum [k + 1])){
                return k;
            }
        }
        return -1;
    }
}
